package lc;
import java.util.*;


import org.junit.*;
public class Ex93 {
    class Solution2 {
        public List<String> restoreIpAddresses(String s) {
            len = s.length();
            dfs(4, new ArrayList<>(), s, 0);
            return res;
        }
    
        List<String> res = new ArrayList<>();
        int len;
        public void dfs(int segs, List<String> cur, String ori, int idx) {
            int remain = len - idx;
            if (segs == 1) {
                if (remain > 3) return;
                cur.add(ori.substring(idx));
                res.add(join(cur));
                cur.remove(cur.size() - 1);
                return;
            }
            if (remain < segs || remain > segs * 3) {
                //不够接下来分得，或者太多了分不完，进行回溯
                return;
            }
            char c = ori.charAt(idx);
            if (c == '0') {
                //只能添加一种方案
                cur.add("0");
                dfs(segs - 1, cur, ori, idx + 1);
                cur.remove(cur.size() - 1);
                return;
            }
            for (int i = 1; i <= 3; i++) {
                //当前取出1到3位作为这轮的划分
                String s = ori.substring(idx, idx + i);
                if (Integer.parseInt(s) > 255) {
                    break;
                }
                cur.add(s);
                dfs(segs - 1, cur, ori, idx + i);
                cur.remove(cur.size() - 1);
            }
        }

        public String join(List<String> ss) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < ss.size(); i++) {
                sb.append(ss.get(i) + ".");

            }
            return sb.substring(0, sb.length() - 1);
        }
    }

    class Solution {
        public List<String> restoreIpAddresses(String s) {
            res = new ArrayList<>();
            len = s.length();
            dfs(s, 0, "", 4);
            return res;
        }
        List<String> res;
        int len;
        public void dfs(String s, int idx, String cur, int t) {
            if (t == 1) {
                if (len - idx > 3 || s.charAt(idx) == '0') return;
                String tmp = s.substring(idx);
                if (Integer.parseInt(tmp) > 255) return;
                cur += tmp;

                res.add(cur);
                return;
            }

            if (s.charAt(idx) == '0') {
                dfs(s, idx + 1, cur + "0.", t - 1);
                return;
            }

            //便利三個取值，求下個位置
            for (int i = 1; i <= 3; i++) {
                if (idx + i >= len) break;
                int tmp = Integer.parseInt(s.substring(idx, idx + i));
                if (tmp > 255) break;
                dfs(s, idx + i, cur + tmp + ".", t - 1);
            }
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        System.out.println(s.restoreIpAddresses("25525511135"));        
    }
}
